Homework 2, Due Date: Nov. 11th, 7 PM, using SUBMIT command.

Assigned: 30 Oct. 2003
Note: Submit a PDF/PS file of a TYPEWRITTEN (or Wordprocessor-based) or scanned handwritten (should be legible to be eligible for grading) homework. If hand-written document is not scanning well, it can be turned in class PRIOR to above deadline.
The command to run is specific to your section:

Answer the following questions. Note that the problem numbers refer to OSC, 6th Ed, XP Update Edition.

  1. Problem 7.8: The Sleeping-Barber Problem. A barbershop consists of a waiting room with n chairs and the barber room containing the barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. Write a program to coordinate the barber and the customers.
  2. Problem 7.15. A file is to be shared among different processes, each of which has a unique number. The file can be accessed simultaneously by several processes, subject to the following constraint: The sum of all unique numbers associated with all the processes currently accessing the file must be less than n. Write a monitor to coordinate access to the file.
  3. Problem 7.18. Why does Solaris implement multiple locking mechanisms? Under what circumstances does it use spinlocks, semaphores, adaptive mutexes, conditional variables, and readers-writers locks? Why does it use each mechanism? What is the purpose of turnstiles
  4. Problem 8.4  Consider the traffic deadlock depicted in Figure 8.8 (please see the book for this Picture).
    1. Show that the four necessary conditions for deadlock indeed hold in this example
    2. State a simple rule that will avoid deadlocks in this system.
  5. Problem 8.6 In a real computer system, neither the resources available nor the demands of processes for resources are consistent over long periods (months). Resources break or are replaced, new processes come and go, new resources are bought and added to the system. If deadlock is controlled by the banker's algorithm, which of the following changes can be made safely (without introducing the possibility of deadlock), and under what circumstances?
    1. Increase Available (new resources added)
    2. Decrease Available (resource permanently removed from system)
    3. Increase Max for one process (the process needs more resources than allowed, it may want more)
    4. Decrease Max for one process (the process decides it does not need that many resources)
    5. Increase the number of processes.
    6. Decrease the number of processes.
  6. Problem 8.9: Consider a system consisting of m resources of the same type, being shared by n processes. Resources can be requested and released by processes only one at a time. Show that the system is deadlock-free if the following two conditions hold:
    1. The maximum need of each process is between 1 and m resources.
    2. The sum of all maximum needs is less than m+n.
  7. Problem 8.13 Consider the following snapshot of a system:

Allocation                                   Max                                 Available

----------------                         -------------------                       ----------------

A   B  C   D                            A   B  C   D                         A   B  C   D

                                                               P0           0   0  1    2                             0   0    1    2                         1    5    2   0

                                                               P1           1   0   0   0                             1    7    5   0 

                                               P2           1   3   5   4                              2   3    5   6

                                               P3           0    6   3   2                             0   6    5    2

                                               P4           0    0    1   4                            0   6   5    6

Answer the following  questions using the banker’s algorithm:

a: What is the content of the matrix Need?

b: Is the system in a safe state?

c:If a request from process P1 arrives for (0,4,2,0), can the request be granted immediately?